package com.zhugang.week13.stack;

import java.util.Stack;

/**
 * @program algorithms
 * @description: Calculate
 * @author: chanzhugang
 * @create: 2022/11/01 20:54
 */
public class Calculate {

    /**
     * 面试题 16.26 计算器 求表达式值，比较考验编码能力，小细节处理多，抽出方法
     * https://leetcode.cn/problems/calculator-lcci/
     *
     * @param s
     * @returnx
     */
    public int calculate(String s) {
        /**
         * 画图总结：定义两个栈，数字栈、符号栈
         * 1、数字直接数字栈；
         * 2、运算符c > 栈顶元素 c直接入栈；
         * 3、运算符c <= 栈顶运算符 栈顶出栈计算，值压入数字栈
         */
        Stack<Integer> numStack = new Stack<>();
        Stack<Character> opsStack = new Stack<>();
        int i = 0;
        int n = s.length();
        while (i < n) {
            char c = s.charAt(i);
            if (c == ' ') {
                i++;
            } else if (isDigit(c)) {
                // 第一步 数字：多个字符计算为数字
                int num = 0;
                while (i < n && isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                numStack.push(num);
            } else {
                // 运算符
                if (opsStack.isEmpty() || prior(c, opsStack.peek())) {
                    // 第二步
                    opsStack.push(c);
                } else {
                    // 第三步：取出栈顶元素计算
                    while (!opsStack.isEmpty() && !prior(c, opsStack.peek())) {
                        fetchAndCal(numStack, opsStack);
                    }
                    opsStack.push(c);
                }
                i++;
            }
        }

        while (!opsStack.isEmpty()) {
            // 还有运算符，可以继续计算
            fetchAndCal(numStack, opsStack);
        }
        return numStack.pop();

    }

    private void fetchAndCal(Stack<Integer> numStack, Stack<Character> opsStack) {
        Integer num2 = numStack.pop();
        Integer num1 = numStack.pop();
        Character ops = opsStack.pop();

        int ret = cal(ops, num1, num2);
        //  计算完的值压入数字栈
        numStack.push(ret);
    }

    private int cal(Character ops, Integer num1, Integer num2) {
        return switch (ops) {
            case '+' -> num1 + num2;
            case '-' -> num1 - num2;
            case '*' -> num1 * num2;
            default -> num1 / num2;
        };
    }

    private boolean prior(char a, char b) {
        if ((a == '*' || a == '/') && (b == '+' || b == '-')) {
            return true;
        }
        return false;
    }

    private boolean isDigit(char c) {
        // 注意这里是字符
        return c >= '0' && c <= '9';
    }

    public static void main(String[] args) {
        Calculate calculate = new Calculate();
        int res = calculate.calculate("5+3*2+1-2*3-4");
        System.out.println(res);
    }
}